//Serialization is the process of converting a data structure or object into a s
//equence of bits so that it can be stored in a file or memory buffer, or transmit
//ted across a network connection link to be reconstructed later in the same or an
//other computer environment. 
//
// Design an algorithm to serialize and deserialize a binary tree. There is no r
//estriction on how your serialization/deserialization algorithm should work. You 
//just need to ensure that a binary tree can be serialized to a string and this st
//ring can be deserialized to the original tree structure. 
//
// Clarification: The input/output format is the same as how LeetCode serializes
// a binary tree. You do not necessarily need to follow this format, so please be 
//creative and come up with different approaches yourself. 
//
// 
// Example 1: 
//
// 
//Input: root = [1,2,3,null,null,4,5]
//Output: [1,2,3,null,null,4,5]
// 
//
// Example 2: 
//
// 
//Input: root = []
//Output: []
// 
//
// Example 3: 
//
// 
//Input: root = [1]
//Output: [1]
// 
//
// Example 4: 
//
// 
//Input: root = [1,2]
//Output: [1,2]
// 
//
// 
// Constraints: 
//
// 
// The number of nodes in the tree is in the range [0, 104]. 
// -1000 <= Node.val <= 1000 
// 
// Related Topics 树 深度优先搜索 广度优先搜索 设计 字符串 二叉树 
// 👍 650 👎 0


package leetcode.editor.cn;

import java.util.*;

//Java：Serialize and Deserialize Binary Tree
class P297SerializeAndDeserializeBinaryTree {
    public static void main(String[] args) {
        Codec solution = new P297SerializeAndDeserializeBinaryTree().new Codec();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(5);
        String serialize = solution.serialize(root);
//        "1>>2>>3>>null>>null>>4>>5>>"
        solution.deserialize(serialize);

        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    public class Codec {

        // Encodes a tree to a single string.
        public String serializeBFS(TreeNode root) {
            if (root == null) {
                return "null";
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            StringBuilder sb = new StringBuilder();
            while (!queue.isEmpty()) {
                int size = queue.size();
                while (size-- > 0) {
                    TreeNode poll = queue.poll();
                    if (poll == null) {
                        sb.append("null" + ">>");
                    } else {
                        sb.append(poll.val + ">>");
                        queue.offer(poll.left);
                        queue.offer(poll.right);
                    }
                }
            }
            return sb.toString();
        }

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) {
                return "null";
            }
            StringBuilder sb = new StringBuilder();
            serialize(root, sb);
            return sb.toString();
        }

        private void serialize(TreeNode root, StringBuilder sb) {
            if (root == null) {
                sb.append("null" + ">>");
            } else {
                sb.append(root.val + ">>");
                serialize(root.left, sb);
                serialize(root.right, sb);
            }
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if ("null".equals(data)) {
                return null;
            }
            String[] arr = data.split(">>");
            TreeNode root = deserialize(new ArrayList(Arrays.asList(arr)));
            return root;
        }

        private TreeNode deserialize(List<String> list) {
            if (list.isEmpty()) {
                return null;
            }
            String remove = list.remove(0);
            TreeNode root = null;
            if (!remove.equals("null")) {
                root = new TreeNode(Integer.parseInt(remove));
                root.left = deserialize(list);
                root.right = deserialize(list);

            }
            return root;

        }

        // Decodes your encoded data to tree.
        public TreeNode deserializeBFS(String data) {
            if ("null".equals(data)) {
                return null;
            }
            String[] arr = data.split(">>");
            TreeNode root = new TreeNode(Integer.parseInt(arr[0]));
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            for (int i = 1; i < arr.length; i++) {
                TreeNode parent = queue.poll();
                if (!arr[i].equals("null")) {
                    parent.left = new TreeNode(Integer.parseInt(arr[i]));
                    queue.offer(parent.left);
                }
                i++;
                if (!arr[i].equals("null")) {
                    parent.right = new TreeNode(Integer.parseInt(arr[i]));
                    queue.offer(parent.right);
                }
            }
            return root;
        }
    }

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
//leetcode submit region end(Prohibit modification and deletion)

}